package com.java.basic.datastruct;

import java.util.Arrays;
import java.util.Iterator;

public class SortLineTableTest {
    public static void main(String[] args) {
        SortLineTable<Integer> lineTable = new SortLineTable<Integer>();
       // lineTable.add(new Object());
        lineTable.add(75);
        lineTable.add(75);
        lineTable.add(75);
        lineTable.add(68);
        lineTable.add(100);
        System.out.println(Arrays.asList(lineTable.array));
        SortLineTable<Integer> lineTable2 = new SortLineTable<Integer>();
        lineTable2.add(175);
        lineTable2.add(75);
        lineTable2.add(175);
        lineTable2.add(68);
        lineTable2.add(1001);
        lineTable.addAll(lineTable2);
        System.out.println(Arrays.asList(lineTable.array));
        for (Object a : lineTable) {
            System.out.println(a);
        }
    }

    private static class SortLineTable<T> implements Iterable<T> {
        private Comparable[] array;
        private Integer capacity;

        public SortLineTable() {
            this.capacity = 0;
            this.array = null;
        }

        public boolean add(T a) {
            if (a == null || !(a instanceof Comparable)) return false;
            if (this.capacity == 0) {
                this.array = new Comparable[]{(Comparable) a};
            } else if (this.capacity > 0) {
                int fi = findIndex((Comparable) a, 0, this.capacity - 1);
                Comparable[] newArray = new Comparable[this.capacity + 1];
                if (fi == 0) {
                    System.arraycopy(this.array, 0, newArray, 1, this.capacity);
                    newArray[0] = (Comparable) a;
                } else if (fi >= this.capacity) {
                    System.arraycopy(this.array, 0, newArray, 0, fi);
                    newArray[fi] = (Comparable) a;
                } else {
                    System.arraycopy(this.array, 0, newArray, 0, fi);
                    System.arraycopy(this.array, fi, newArray, fi + 1, this.capacity - fi);
                    newArray[fi] = (Comparable) a;
                }
                this.array = newArray;
            }
            this.capacity += 1;
            return true;
        }

        public SortLineTable<Integer> findEle(T ele) {
            if (ele == null || !(ele instanceof Comparable) || this.isEmpty()) return null;
            int index = findIndex((Comparable) ele, 0, this.capacity - 1);
            SortLineTable<Integer> table = new SortLineTable<Integer>();
            index--;
            while (index >= 0) {
                Comparable comparable = this.array[index];
                if (comparable.compareTo(ele) == 0) {
                    table.add(index);
                } else {
                    break;
                }
                index--;
            }
            return table.isEmpty() ? null : table;
        }


        public boolean removeFirstEle(T ele) {
            SortLineTable<Integer> lineTable = findEle(ele);
            if (lineTable != null && lineTable.array != null) {
                if (this.capacity == 1) {
                    this.capacity = 0;
                    this.array = null;
                } else {
                    Integer fi = lineTable.getIndex(0);
                    int newCapacity = this.capacity - 1;
                    Comparable[] newArray = new Comparable[newCapacity];
                    if (fi == 0) {
                        System.arraycopy(array, 1, newArray, 0, newCapacity);
                        this.array = newArray;
                        this.capacity = newCapacity;
                    } else if (fi == newCapacity) {
                        System.arraycopy(array, 0, newArray, 0, fi);
                        this.array = newArray;
                        this.capacity = newCapacity;
                    } else {
                        System.arraycopy(array, 0, newArray, 0, fi);
                        System.arraycopy(array, fi + 1, newArray, fi, newCapacity - fi);
                        this.array = newArray;
                        this.capacity = newCapacity;
                    }
                }
                return true;
            }
            return false;
        }

        public boolean removeAllEle(T ele) {
            boolean del = false;
            while (true) {
                if (!removeFirstEle(ele)) {
                    break;
                }
                del = true;
            }
            return del;
        }

        public T getIndex(Integer index) {
            if (index < 0 || index > this.capacity - 1) {
                return null;
            } else {
                return (T) this.array[index];
            }
        }

        public boolean isEmpty() {
            return this.capacity <= 0;
        }

        private int findIndex(Comparable a, int start, int end) {
            int middleIndex = (end - start) / 2 + start;
            Comparable c = this.array[middleIndex];
            if (a.compareTo(c) >= 0) {
                if (middleIndex + 1 >= end) {
                    if (a.compareTo(this.array[end]) >= 0) {
                        return end + 1;
                    } else {
                        return end;
                    }
                }
                return findIndex(a, middleIndex + 1, end);
            } else {
                if (middleIndex - 1 <= start) {
                    if (a.compareTo(this.array[start]) < 0) {
                        return start;
                    } else {
                        return start + 1;
                    }
                }
                return findIndex(a, start, middleIndex - 1);
            }
        }

        @Override
        public Iterator<T> iterator() {
            return (Iterator<T>) Arrays.stream(this.array).iterator();
        }


        public boolean addAll(SortLineTable<T> lineTable){
           Integer capacity1 = lineTable.capacity;
           if(capacity1<=0)return false;
            for (T t : lineTable) {
                this.add(t);
            }
           return true;
        }
    }
}
